package leetcode_1101_1200;

import java.util.*;

public class LeeCode_1125_2 {
    public static void main(String[] args) {
        List<List<String>> p1 = new ArrayList<>();
        ArrayList<String> p11 = new ArrayList<>();
        p11.add("java");
        p1.add(p11);
        ArrayList<String> p12 = new ArrayList<>();
        p12.add("nodejs");
        p1.add(p12);
        ArrayList<String> p13 = new ArrayList<>();
        p13.add("nodejs");
        p13.add("reactjs");
        p1.add(p13);
    }
    private long all;
    private int[] mask;
    private long[][] memo;
    private int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        Map<String, Integer> sid = new HashMap<>();
        int m = req_skills.length;
        for (int i = 0; i < m; i++) {
            sid.put(req_skills[i], i);
        }
        int n = people.size();
        mask = new int[n];
        for (int i = 0; i < n; i++) {
            for (String s : people.get(i)) {
                mask[i] |= 1 << sid.get(s);
            }
        }
        int u = 1 << m;
        memo = new long[n][u];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1); //没计算过
        }
        all = (1L << n) - 1;
        long res = dfs(n - 1, u - 1);
        int[] ans = new int[Long.bitCount(res)];
        for (int i = 0, j = 0; i < n; i++) {
            if (((res >> i) & 1) > 0){
                ans[j++] = i;
            }
        }
        return ans;
    }
    private long dfs(int i, int j){
        if (i == 0)
            return 0;
        if (i < 0)
            return all;
        if (memo[i][j] != -1)
            return memo[i][j];
        long res = dfs(i - 1, j); //不选i
        long res2 = dfs(i - 1, j & mask[i]) | (1L << i); // 选 mask[i]
        return memo[i][j] = Long.bitCount(res) < Long.bitCount(res2) ? res : res2;
    }
}
